from IPython.display import Image
import numpy as np
from sklearn.manifold import TSNE
import io
import base64
from IPython.display import HTML
import matplotlib.cm as cm
import matplotlib.colors as mcolors
import matplotlib.pyplot as plt
import numpy
import matplotlib.pyplot as plt
import time
def draw_scatter_plot(*args, clusters=None, color=None, labels=None, title="", size=5):
"""draw_scatter_plot(data1, data2, color=["color1", "color2"], labels=["label1", "label2"])
draw_scatter_plot(dataset, 2, color=["color1", "color2"], ...)
draw_scatter_plot(tsne_lda, clusters=topic_num)"""
n_of_datasets = args[-1]
if(isinstance(n_of_datasets, int) and len(args)-1 == 1 and clusters is None):
#podział args na n_of_datasets czesci
dataset = to_point_list(args[0])
jump = (len(dataset)+1) // n_of_datasets
data_list = [dataset[begin:begin+jump] for begin in range(0, len(dataset), jump)]
elif(not isinstance(n_of_datasets, int) and clusters is None):
data_list = list(args)
n_of_datasets = len(args)
elif(not isinstance(n_of_datasets, int) and clusters is not None):
n_of_datasets = len(args)
data_list = ([c for c in args[0]])
color = cm.rainbow(np.linspace(0, 1, np.max(clusters)+1))
sortList = list(zip(data_list,clusters))
def sortKey(val):
return val[1]
sortList.sort(key=sortKey)
iterVal = sortList[0][1]
data_list = []
local_data_list = []
for pointData in sortList:
if(pointData[1] == iterVal):
# 1 color
local_data_list.append(pointData[0])
else:
# 2nd color
iterVal = pointData[1]
data_list.append(local_data_list)
local_data_list = []
local_data_list.append(pointData[0])
data_list.append(local_data_list)
data_list = np.array(data_list)
n_of_datasets = len(data_list)
#print("n_of_datasets", n_of_datasets)
#print("color", len(color))
else:
raise BaseException("wrong data input format, diferent input :(")
if(color is None or len(color) != n_of_datasets):
if(color is not None and len(color) != n_of_datasets): print("WARNING: wrong color format, overwriting")
color = cm.rainbow(np.linspace(0, 1, n_of_datasets))
color = [[c] for c in color]
show_legend = True
if(labels is None):
labels = [" "] * n_of_datasets
show_legend = False
#if(clusters is not None and labels is not None):
# data_list - list of datasets;
dims = len(to_1dim_list(data_list[0]))
#print(dims)
for data in data_list:
if(dims != len(to_1dim_list(data))): raise BaseException("wrong data format, diferent dimensions :(")
plt.figure();
if(dims == 3): ax = plt.subplot(111, projection='3d')
#print(len(data_list), len(color))
for ind, data in enumerate(data_list):
points = to_1dim_list(data)
if(dims == 1):
plt.scatter(points[0], [0]*len(points[0]), c=color[ind], s=size, label=labels[ind]);
elif(dims == 2):
plt.scatter(points[0], points[1], c=color[ind], s=size, label=labels[ind]);
elif(dims == 3):
ax.scatter3D(points[0], points[1], points[2], c=color[ind], s=size, label=labels[ind])
else:
raise BaseException("wrong data format :(")
plt.title(title);
if(show_legend): plt.legend();
plt.rcParams['figure.figsize'] = [15, 10]
plt.show();
def to_1dim_list(point_list, force = False):
# [(x1,y1,..),(x2,y2,...),(x3,y3,..)] ==>> [[x1,x2,x3,...],[y1,y2,...],...]
if(force): return list(zip(*point_list))
if(isinstance(point_list[0], int)): return [point_list]
if(len(point_list) > len(point_list[0])):
return list(zip(*point_list))
else:
return point_list
def largeVis_plot(infile, labelfile, outfile, range=''):
label = []
for line in open(labelfile, "r"):
label.append(line.strip())
N = M = 0
all_data = {}
for i, line in enumerate(open(inputfile)):
vec = line.strip().split(' ')
if i == 0:
N = int(vec[0])
M = int(vec[1])
elif i <= N:
if labelfile == '':
label.append(0)
all_data.setdefault(label[i-1], []).append((float(vec[-2]), float(vec[-1])))
colors = plt.cm.rainbow(numpy.linspace(0, 1, len(all_data)))
for color, ll in zip(colors, sorted(all_data.keys())):
x = [t[0] for t in all_data[ll]]
y = [t[1] for t in all_data[ll]]
plt.rcParams['figure.figsize'] = [15, 10]
plt.plot(x, y, '.', color = color, markersize = 4)
if range != '':
l = abs(float(args.range))
plt.xlim(-l, l)
plt.ylim(-l, l)
plt.savefig(outfile, dpi = 500)
Dotychczas poznaliśmy metody które działają dobrze na małych lub średnich zbiorach (dajmy na to ~2000 punktów i ~4 wymiary)
Problem wizualizacji danych robi się uciążliwy, kiedy mamy zarówno bardzo dużą ilość punktów jak i wymiarów, a metody redukcji wymiarowości (PCA/kPCA, MDS, etc) nie przynoszą spodziewanych rezultatów. Przykładowo: mamy 100 wymiarów, a po transformacji PCA do zachowania 80% informacji nadal potrzebujemy uwzględnić 90 wymiarów. Nie ma wówczas możliwości przygotowania danych tak, żeby tSNE sobie z nimi poradziło w rozsądnym czasie. W obliczu braku dostępu do zasobów obliczeniowych często taka procedura trwa dłużej niż byłoby to praktyczne. To co w tym przypadku stanowi obliczeniowe wąskie gardło to krok tworzenia grafu podobieństwa.
Dla tSNE jest to O(dN^2), a dla bhSNE O(NlogN), gdzie d - liczba wymiarów
Na tę bolączkę stara się odpowiedzieć largeVis.
link do publikacji: https://arxiv.org/pdf/1602.00370.pdf
dyskusja na Hacker News: https://news.ycombinator.com/item?id=11656133
Image("./img/knn_typical.png")
Podstawowy mechanizm: tworzenie grafu podobieństwa między punktami
Problem: złożoność obliczeniowa tego kroku (właśnie z tego powodu tSNE nie skaluje się dobrze do np miliona punktów z setkami wymiarów)
Bechmarki dla różnych metod kNN: https://github.com/erikbern/ann-benchmarks
Redukcja wymiarowości otrzymanego grafu kNN do 2 albo 3
Dwa podstawowe podejścia: transforamcje liniowe (np. PCA) oraz nieliniowe (np. MDS)
Metody nieliniowe lepsze od liniowych, ale 1. złożonosć i 2. słabo sobie radzą z prawdziwymi (==niespreparowanymi) danymi
Metoda nieliniowa która dobrze działa na realnych danych: tSNE. Jest ona jednak słabo skalowalna, ponadto jest wrażliwa na zmianę parametrów. Przy optymalizacjach da się podnieść wydajność kroku konstrukcji KNN w tSNE do O(NlogN)
Opiera się głównie na założeniu "the neighbour of my neighbour is also likely to be my neighbour"
Nie konstruujemy nowego grafu, tylko staramy się ulepszyć dokładność pewnego już istniejącego grafu
Buduje się kilka random projection trees żeby zbudować przybliżony graf KNN. Na tym etapie jego dokładność jest niewielka
Następnie dla każdgo wierzchołka w grafie przeszukujemy sąsiadów jego sąsiadów. Można ten krok powtórzyć w kilku iteracjach żeby zwiększyć dokładność.
Siła podejścia polega na tym że potrzeba tylko kilku iteracji aby dokładność grafu zbliżyła się do 100%.
Mając już graf kNN, trzeba go zwizualizować. Bez wchodzenia w szczegóły dokonuje się tego za pomocą funkcji probalistycznej, która jest optymalizowana przy pomocy stochastic gradient descent. Dzięki temu udaje się zejść ze złożonością tego kroku do O(N).
Image("./img/knn_graph_iterations.png")
# Konstrukcja grafu kNN
Image("./img/knn_graph_construction_times.png")
# klasyfikacja punktów 2D
Image("./img/graph_visualization.png")
video = io.open('./img/mnist.mov', 'r+b').read()
encoded = base64.b64encode(video)
HTML(data='''<video alt="test" controls>
<source src="data:video/mp4;base64,{0}" type="video/mp4" />
</video>'''.format(encoded.decode('ascii')))